package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;

import Tree.CreateByPreAndIn;
import Tree.TreeNode;

public class MostFrequentSubtreeSum {

	public static void main(String[] args) {
		int[] pre = {2, -5, 8, -3, 7, 9};
		int[] in = {8, -5, 2, 7, -3, 9};
		TreeNode root = CreateByPreAndIn.reConstructBinaryTree(pre, in);
		MostFrequentSubtreeSum object = new MostFrequentSubtreeSum();
		object.findFrequentTreeSum(root);
	}
	
	List<Integer> sum = new ArrayList<>();
	public int[] findFrequentTreeSum(TreeNode root) {
        if(root == null){
            return null;
        }
        sum.clear();
        sum.add(getSum(root));
        HashMap<Integer, Integer> map = new HashMap<>();
        int max = Integer.MIN_VALUE;
        for (Integer subtreeSum : sum) {
			map.put(subtreeSum, map.getOrDefault(subtreeSum, 0) + 1);
			max = Math.max(max, map.get(subtreeSum));
		}
        sum.clear();
        for(Entry<Integer, Integer> entry : map.entrySet()){
        	if(entry.getValue() == max){
        		sum.add(entry.getKey());
        	}
        }
        int length = sum.size();
        int[] res = new int[length];
        for (int i = 0; i < length; i++) {
			res[i] = sum.get(i);
		}
        return res;
    }

	public int getSum(TreeNode node) {
		if (node == null) {
			return 0;
		}
		int left = 0;
		int right = 0;
		if (node.left != null) {
			left = getSum(node.left);
			sum.add(left);
		}
		if (node.right != null) {
			right = getSum(node.right);
			sum.add(right);
		}
		int res = node.val + left + right;
		return res;
	}
}
